package shenrudigui;

public class _03硬币表示 {
    /**
     * 假设我们有8种不同面值的硬币｛1，2，5，10，20，50，100，200｝，用这些硬币组合构成一个给定的数值n。
     * 例如n=200，那么一种可能的组合方式为 200 = 3 * 1 + 1＊2 + 1＊5 + 2＊20 + 1 * 50 + 1 * 100.
     * 问总共有多少种可能的组合方式？ (这道题目来自著名编程网站ProjectEuler) 类似的题目还有：
     * <p>
     * 　　[华为面试题] 1分2分5分的硬币三种，组合成1角，共有多少种组合
     * 1*x + 2*y + 5*z=10
     * 　　[创新工厂笔试题] 有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n分钱，有多少组合可以组成n分钱
     * <p>
     * 1 5 10 25 分 n,多少种组合方法.
     */
    public static void main(String[] args) {
        for (int i = 1; i < 101;i++){
            int ways = countWays1(i);
            System.out.println( i + "--------" + ways);
        }
    }

    public static int countWays(int n) {
        if (n <= 0) return 0;
        return countWaysCore(n, new int[]{1, 5, 10, 25}, 3);
    }

    /**
     * @param n     需要凑的数目
     * @param coins 有哪些面值
     * @param cur   当前面值可选的范围
     * @return
     */
    public static int countWaysCore(int n, int[] coins, int cur) {
        if (cur == 0) return 1;
        int res = 0;
        //目标面值除候选面值的最大面值，算出可以拿多少个最大面值的次数。再递归目标面值-已选面值
        //要么不选  要么选1个  要么选2个 .....
        for (int i = 0; i * coins[cur] <= n; i++) {
            int shengyu = n - i * coins[cur];
            res += countWaysCore(shengyu, coins, cur - 1);
        }
        return res;
    }

    /*递推解法*/
    public static int countWays1(int n) {

        int[] coins = {1, 5, 10, 25};
        int[][] dp = new int[4][n + 1];//前i种面值,组合出面值j
        for (int i = 0; i < 4; i++) {
            dp[i][0] = 1;//凑出面值0,只有一种可能,第一列初始化为1
        }
        for (int j = 0; j < n + 1; j++) {
            dp[0][j] = 1;//用1来凑任何面值都只有一种凑法,第一行初始化为1
        }
        for (int i = 1; i < 4; i++) {
            for (int j = 1; j < n + 1; j++) {
                for (int k = 0; k <= j / coins[i]; ++k) {
                    dp[i][j] += dp[i - 1][j - k * coins[i]];
                }
            }
        }
        return dp[3][n];
    }
}
